package 岛屿问题;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

/**
 * @author: AirMan
 * @date: 2025/6/3 20:24
 * @description:
 * 给定一个由 1（陆地）和 0（水）组成的矩阵，你最多可以将矩阵中的一格水变为一块陆地，
 * 在执行了此操作之后，矩阵中最大的岛屿面积是多少。
 * 岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿是被水包围，并且通过水平方向或垂直
 * 方向上相邻的陆地连接而成的。你可以假设矩阵外均被水包围。
 * 输入描述：
 * 第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。
 * 输出描述：
 * 输出一个整数，表示最大的岛屿面积
 */
public class Solution7 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        int[][] graph = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                graph[i][j] = sc.nextInt();
            }
        }


        // 第一遍遍历所有的岛屿，并且为计算每一个岛屿的面积；通过Map存放，key为岛屿的编号，value为岛屿的面积
        int k = 2; // 岛屿编号
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (graph[i][j] == 1) {
                    map.put(k, 0);  // 存放岛屿面积
                    dfs(graph, i, j, k, map); // 这里的if判断优化了visited数组，因为我们会将陆地进行编号，访问过之后陆地就不是1了
                    k++; // 岛屿数量加一
                }
            }
        }

        // 第二遍遍历所有的水域，然后计算如果将该水域修改为陆地之后，它与之接壤的岛屿组成的面积（如果存放与之接壤的岛屿），然后取最大值
        int result = map.getOrDefault(2, 0); // 记录修改过程中的最大值（即结果）
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (graph[i][j] == 0) {
                    // 计算左右上下相邻岛屿的面积
                    Set<Integer> set = new HashSet<>();
                    int left = 0, right = 0, above = 0, below = 0;
                    if (j > 0) {
                        int leftIndex = graph[i][j - 1];
                        set.add(leftIndex);
                        left = map.getOrDefault(leftIndex, 0);
                    }
                    if (j < m - 1) {
                        int rightIndex = graph[i][j + 1];
                        if (!set.contains(rightIndex)) {
                            set.add(rightIndex);
                            right = map.getOrDefault(rightIndex, 0);
                        }
                    }
                    if (i > 0) {
                        int aboveIndex = graph[i - 1][j];
                        if (!set.contains(aboveIndex)) {
                            set.add(aboveIndex);
                            above = map.getOrDefault(aboveIndex, 0);
                        }
                    }
                    if (i < n - 1) {
                        int belowIndex = graph[i + 1][j];
                        if (!set.contains(belowIndex)) {
                            below = map.getOrDefault(belowIndex, 0);
                        }
                    }
                    result = Math.max(result, left + right + above + below + 1);
                }
            }
        }
        System.out.println(result);

    }

    private static void dfs(int[][] graph, int x, int y, int k, HashMap<Integer, Integer> map) {
        if (x < 0 || x >= graph.length || y < 0 || y >= graph[0].length) return; // 左边越界
        if (graph[x][y] != 1) return; // 左边为水域或已经被访问过了
        // 访问该节点，并更新岛屿面积
        graph[x][y] = k;
        map.put(k, map.get(k) + 1);
        // 往四个方向进行 dfs 遍历，寻找岛屿
        dfs(graph, x - 1, y, k, map); // left
        dfs(graph, x + 1, y, k, map); // right
        dfs(graph, x, y + 1, k, map); // above
        dfs(graph, x, y - 1, k, map); // below
    }

}
